TNotes.leetcode

Appearance

⏰0788. 旋转数字【中等】

0788. 旋转数字【中等】 ​

1. 📝 题目描述 ​

我们称一个数 X 为好数, 如果它的每位数字逐个地被旋转 180 度后，我们仍可以得到一个有效的，且和 X 不同的数。要求每位数字都要被旋转。

如果一个数的每位数字被旋转以后仍然还是一个数字，则这个数是有效的。0, 1, 和 8 被旋转后仍然是它们自己；2 和 5 可以互相旋转成对方（在这种情况下，它们以不同的方向旋转，换句话说，2 和 5 互为镜像）；6 和 9 同理，除了这些以外其他的数字旋转以后都不再是有效的数字。

现在我们有一个正整数 N, 计算从 1 到 N 中有多少个数 X 是好数？

示例：

txt
输入: 10
输出: 4
解释:
在[1, 10]中有四个好数：2, 5, 6, 9。
注意 1 和 10 不是好数, 因为他们在旋转之后不变。

提示：

  • N 的取值范围是 [1, 10000]。

2. 🎯 s.1 - 枚举 ​

c
bool isGood(int num) {
    bool diff = false;
    while (num > 0) {
        int d = num % 10;
        if (d == 3 || d == 4 || d == 7) return false;
        if (d == 2 || d == 5 || d == 6 || d == 9) diff = true;
        num /= 10;
    }
    return diff;
}

int rotatedDigits(int n) {
    int res = 0;
    for (int i = 1; i <= n; i++) {
        if (isGood(i)) res++;
    }
    return res;
}
js
/**
 * @param {number} n
 * @return {number}
 */
var rotatedDigits = function (n) {
  let res = 0
  for (let i = 1; i <= n; i++) {
    if (isGood(i)) res++
  }
  return res
}

function isGood(num) {
  let diff = false
  while (num > 0) {
    const d = num % 10
    if (d === 3 || d === 4 || d === 7) return false
    if (d === 2 || d === 5 || d === 6 || d === 9) diff = true
    num = Math.floor(num / 10)
  }
  return diff
}
py
class Solution:
    def rotatedDigits(self, n: int) -> int:
        def is_good(num: int) -> bool:
            diff = False
            while num > 0:
                d = num % 10
                if d in (3, 4, 7):
                    return False
                if d in (2, 5, 6, 9):
                    diff = True
                num //= 10
            return diff
        return sum(1 for i in range(1, n + 1) if is_good(i))
  • 时间复杂度：O(nlog⁡n)，每个数检查其位数
  • 空间复杂度：O(1)

算法思路：

  • 有效字符：0,1,8 旋转后不变；2,5,6,9 旋转后变化；3,4,7 无效
  • 枚举 1~n，若数字只包含有效字符且至少包含一个变化字符，则计数 +1